The present invention relates to navigation systems and more particularly the present invention relates to ways to represent routes that reduces the amount of data required to fully represent the route for the navigation system.
Navigation systems provide useful features, such as calculating routes to desired destinations and then providing guidance for following the routes. When a navigation system calculates a route to a desired destination, route calculation programming in the navigation system attempts to determine one or more solution routes between a starting location and a destination location. A solution route is formed of a series of connected road segments over which a vehicle can travel from the starting location to the destination location. The solution route calculated by the route calculation programming conforms to known traffic restrictions, such as one-way street restrictions and turn restrictions at intersections. When the route calculation programming in a navigation system calculates a solution route, it accesses a geographic database to obtain data that represent road segments and intersections around and between the starting location and the destination location. The data in the geographic database include information about the locations of roads and intersections, estimated travel times along road segments, the speed limits along roads, turn restrictions, etc. Using these kinds of geographic data, the route calculation programming in navigation systems can find an optimal (e.g., fastest or shortest) route to a specified destination. In one embodiment, the output of the route calculation programming is in the form of an ordered list identifying a plurality of road segments. The plurality of road segments form the continuous navigable route between the origin and the destination that had been calculated by the route calculation programming in the navigation system. The ordered list of road segments is used by the route guidance programming to provide the navigation system user with driving instructions for following the calculated route.
The method described above for representing calculated routes works well for various types of routes and for various types of navigation systems. A consideration associated with the described method for representing routes is that routes that contain a relatively large number of road segments, such as long routes, require a correspondingly large amount of the memory to represent. Although many navigation systems have ample memory resources, some navigation system platforms have relatively small amounts of memory. On navigation system platforms that have relatively small amounts of memory, a long route that has a large number of road segments may occupy a relatively large portion of the memory resources of the navigation system thereby possibly affecting performance.
Another consideration associated with representing a route relates to navigation systems in which a route is calculated at a central location and then data representing the calculated route are transmitted wirelessly to an in-vehicle navigation guidance system that provides the driver with instructions for following the route. With a system in which data representing a route are transmitted wirelessly, a long route having a large number of road segments would require that a relatively large amount of data be transmitted wirelessly thereby requiring that the wireless data transmission system have sufficiently large capacity.
Accordingly, there exists a need to represent routes in a way that reduces the amount of data required to represent the route.
To address these and other objectives, the present invention comprises a method for representing a route along a road network in a geographic region. A database includes data representations of intersections of roads in the geographic region. Associated with the data representation for each intersection of roads are data indicating one or more nominal paths through the intersection. The nominal paths through an intersection identify, for each road segment by which the represented intersection can be entered, one and only one road segment from which the represented intersection is exited. The route along the road network in the geographic region is represented by indicating each intersection at which the route deviates from the nominal path into the intersection.
According to another aspect, the present invention comprises a geographic database including nominal path data associated with represented intersections.
According to another aspect, the present invention comprises a navigation system that uses nominal path data to represent routes.
According to another aspect, the present invention comprises a method for forming a database that includes nominal path data associated with represented intersections.